package com.leetcode.binarytree;

import com.leetcode.datastructure.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2019/10/20
 * @description: 给定一个二叉树，返回它的中序 遍历。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,null,2,3]
 * 1
 * \
 * 2
 * /
 * 3
 * <p>
 * 输出: [1,3,2]
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class BinaryTreeInorderTraversal94B {
	/**
	 * 左-中-右
	 *
	 * @param root
	 * @return
	 */
	public List<Integer> inorderTraversalByRecursive(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		if (root == null) {
			return result;
		}

		if (root.left != null) {
			inorder(root.left, result);
		}
		result.add(root.val);
		if (root.right != null) {
			inorder(root.right, result);
		}
		return result;
	}

	public void inorder(TreeNode root, List<Integer> list) {
		if (root == null) {
			return;
		}

		if (root.left != null) {
			inorder(root.left, list);
		}
		list.add(root.val);
		if (root.right != null) {
			inorder(root.right, list);
		}
	}

	/**
	 * 通过迭代解决二叉树中序遍历问题
	 * todo:思路：1.遍历左子树直到左节点不存在，依次入栈；2.弹出左子树并弹出该节点的父节点，并入栈父节点的右节点；
	 *
	 * @param root
	 * @return
	 */
	public List<Integer> inorderTraversalByIteratively(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		///1.边界条件判断
		if (root == null) {
			return result;
		}
		Stack<TreeNode> stack = new Stack<>();
		TreeNode cur=root;
		while (!stack.isEmpty()||cur!=null){
			///将左子树入栈,知道没有左子树
			while (cur!=null){
				stack.push(cur);
				cur=cur.left;
			}
			///此时栈顶元素已经不存在左子树，即欲将其出栈的元素！
			cur= stack.pop();
			result.add(cur.val);
			///每一个右子树都需要重新判断左子树
			cur=cur.right;
		}


		///2.将左子树入栈
//		stack.push(root);
//		TreeNode cur=root;
//		while (cur.left!=null) {
//			TreeNode tempNode=cur.left;
//			stack.push(tempNode);
//			cur=cur.left;
//		}
//		///3.当栈不为空时，每一次都需要找到最深的左子树
//		while (!stack.isEmpty()){
//			TreeNode tempNode = stack.pop();
//	 		result.add(tempNode.val);
//			if (tempNode.right!=null){
//				stack.add(tempNode.right);
//			}
//		}


		return result;
	}


	@Test
	public void testRecursive() {
		TreeNode root = TreeNode.stringToTreeNode("[1,null,2,3]");
		System.out.println(root);
	}

	@Test
	public void testIterative(){
		TreeNode root = TreeNode.stringToTreeNode("[1,null,2,3]");
		List<Integer> list = inorderTraversalByIteratively(root);
		System.out.println(list);

	}
}
